1. Field of the Invention
The present invention is directed toward software testing, and more particularly to methods and systems for testing for concurrent bugs in multi-threaded computer programs.
2. Background
A computer program may be described as a set of structures or modules, along with their respective relationships and interconnections. Due to the nature of such interconnections, a program may be also described as a hierarchy of several levels. The program set of structures may be distributed over these levels, where each structure is connected to one or more of the structures located in the level above it. Such a hierarchy may be defined by the order that these structures are to be executed. A computer program may contain two or more parallel structures, and a program's structure may include several levels each containing two or more parallel structures.
A thread is a sequence of structures that are to be executed one after the other in a sequential fashion. Thus, a thread may include a sequence of structures that belong to consecutive levels in the hierarchy and are connected to each other. The results generated during the execution of the ordered sequence of a program's structures are the thread's results.
Concurrent programs, also known as multi-threaded programs, may contain inter-thread conflicts that can result in errors or hanging conditions upon execution. Such errors can be particularly difficult to discover during the programming stage. An example of an inter-thread conflict is a data race between parallel threads wherein (1) there exists an execution of two threads such that the executing computer may arrive at a state for which there may be two threads which can execute, (2) both of these threads may access a common variable, and (3) at least one of the accesses may be a write access.
Known approaches to testing concurrent programs include concurrent noise injection, which involves systematically executing program scenarios that are likely to contain race conditions, deadlocks, and other intermittent bugs, collectively referred to as synchronization problems. For example, such techniques may generally involve instrumenting the program by inserting thread-switch forcing code in places that are likely to have concurrent bugs. Such known approaches may affect a program's behavior and thereby expose potential conflicts between threads.
However, such known techniques do not effectively deal with data races that may arise in the context of threads involving non-atomic variables that may have two or more memory words. The reason for this deficiency is that the variable access appears as one instruction, and therefore the instrumentation engine cannot insert thread-switch forcing code in the middle of this access. Accordingly, it would be desirable to provide a system and method that makes it possible to detect or manifest such races that may be associated with non-atomic variables.